|
Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.〔 This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a ''minimum spanning forest'' (a minimum spanning tree for each connected component). This algorithm first appeared in ''Proceedings of the American Mathematical Society'', pp. 48–50 in 1956, and was written by Joseph Kruskal. Other algorithms for this problem include Prim's algorithm, Reverse-delete algorithm, and Borůvka's algorithm. ==Description== * create a forest ''F'' (a set of trees), where each vertex in the graph is a separate tree * create a set ''S'' containing all the edges in the graph * while ''S'' is nonempty and ''F'' is not yet spanning * * remove an edge with minimum weight from ''S'' * * if the removed edge connects two different trees then add it to the forest ''F'', combining two trees into a single tree At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, the forest has a single component and forms a minimum spanning tree. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kruskal's algorithm」の詳細全文を読む スポンサード リンク
|